#include <gtest/gtest.h>
#include "common.h"

using namespace ::std;

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix);
};

// 动态规划
// 更充分的利用前面得到的信息，减少遍历的次数，从而提高算法的速度
// 下一步优化方向：空间优化，可以只保存下一次迭代必要的信息
int Solution::maximalSquare(vector<vector<char>>& matrix) {
    int xLength = matrix.size(), yLength = matrix[0].size();
    int maxBorderLength = 0;
    vector<vector<int>> dp(xLength + 1, vector<int>(yLength + 1, 0));
    for(int i = 1, m = 0; m < xLength; ++i, ++m) {
        for(int j = 1, n = 0; n < yLength; ++j, ++n) {
            if('1' == matrix[m][n]) dp[i][j] = 1 + min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1]));
            if(dp[i][j] > maxBorderLength) maxBorderLength = dp[i][j];
        }
    }
    return maxBorderLength * maxBorderLength;
}

// v02
// int Solution::maximalSquare(vector<vector<char>>& matrix) {
//     int xLength = matrix.size(), yLength = matrix[0].size();
//     int maxBorderLength = 0;
//     vector<vector<int>> dp(xLength + 1, vector<int>(yLength + 1, 0));
//     for(int i = 1, m = 0; m < xLength; ++i, ++m) {
//         for(int j = 1, n = 0; n < yLength; ++j, ++n) {
//             int currentMaxBorderLength = dp[i - 1][j - 1] + 1, k, l;
//             for(k = 0; k < currentMaxBorderLength && '1' == matrix[m - k][n]; ++k) ;
//             for(l = 0; l < currentMaxBorderLength && '1' == matrix[m][n - l]; ++l) ;
//             dp[i][j] = min(currentMaxBorderLength, min(k, l));
//             if(dp[i][j] > maxBorderLength) maxBorderLength = dp[i][j];
//         }
//     }
//     return maxBorderLength * maxBorderLength;
// }

// v01
// int Solution::maximalSquare(vector<vector<char>>& matrix) {
//     int xLength = matrix.size(), yLength = matrix[0].size();
//     int maxBorderLength = 0;
//     vector<vector<int>> dp(xLength, vector<int>(yLength, 0));
//     // for(int i = 0; i < xLength; ++i) dp[i][0] = ('0' == matrix[i][0]) ? 0 : 1;
//     // for(int j = 0; j < yLength; ++j) dp[0][j] = ('0' == matrix[0][j]) ? 0 : 1;
//     for(int i = 0; i < xLength; ++i) {
//         if('0' == matrix[i][0]) {
//             dp[i][0] = 0;
//         } else {
//             dp[i][0] = 1;
//             maxBorderLength = 1;
//         }
//     }
//     for(int j = 0; j < yLength; ++j) {
//         if('0' == matrix[0][j]) {
//             dp[0][j] = 0;
//         } else {
//             dp[0][j] = 1;
//             maxBorderLength = 1;
//         }
//     }
//     for(int i = 1; i < xLength; ++i) {
//         for(int j = 1; j < yLength; ++j) {
//             if('0' == matrix[i][j]) {
//                 dp[i][j] = 0;
//                 continue;
//             }
//             int currentMaxBorderLength = dp[i - 1][j - 1] + 1, k, l;
//             for(k = 1; k < currentMaxBorderLength && '1' == matrix[i - k][j]; ++k) ;
//             for(l = 1; l < currentMaxBorderLength && '1' == matrix[i][j - l]; ++l) ;
//             dp[i][j] = min(currentMaxBorderLength, min(k, l));
//             if(dp[i][j] > maxBorderLength) maxBorderLength = dp[i][j];
//         }
//     }
//     // cout << maxBorderLength << endl;
//     return maxBorderLength * maxBorderLength;
// }

class MaximalSquareCheck : public ::testing::Test {
public:
	class Solution solution;
};

TEST_F(MaximalSquareCheck, testMaximalSquare_1) {
    vector<vector<char>> matrix =  {{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'}};
    EXPECT_TRUE(4 == solution.maximalSquare(matrix));
}

TEST_F(MaximalSquareCheck, testMaximalSquare_2) {
    vector<vector<char>> matrix =  {{'0','1'},{'1','0'}};
    EXPECT_TRUE(1 == solution.maximalSquare(matrix));
}

TEST_F(MaximalSquareCheck, testMaximalSquare_3) {
    vector<vector<char>> matrix =  {{'0'}};
    EXPECT_TRUE(0 == solution.maximalSquare(matrix));
}

TEST_F(MaximalSquareCheck, testMaximalSquare_4) {
    vector<vector<char>> matrix =  {{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'}};
    EXPECT_TRUE(9 == solution.maximalSquare(matrix));
}


int main() {
	::testing::InitGoogleTest();
	return RUN_ALL_TESTS();
}
